package TREE_98;

import java.util.Stack;

import LCommon.TreeNode;

public class Solution {
	public boolean isValidBST_recur(TreeNode root) {
		return helper(root, null, null);
	}

	private boolean helper(TreeNode root, Integer max, Integer min) {
		if (root == null) {
			return true;
		}
		if (max != null && root.val <= max) {
			return false;
		}
		if (min != null && root.val >= min) {
			return false;
		}
		if (!helper(root.right, root.val, min)) {
			return false;
		}
		if (!helper(root.left, max, root.val)) {
			return false;
		}
		return true;
	}

	public boolean isValidBST_order(TreeNode root) {
		Stack<TreeNode> stack = new Stack<TreeNode>();
		double  inorder = - Double.MAX_VALUE;
		while (!stack.isEmpty() || root != null) {
			while (root != null) {
				stack.add(root);
				root = root.left;
			}
			root = stack.pop();
			if (root.val<inorder) {
				return false;
			}
			inorder = root.val;
			root=root.right;
		}
		return true;
	}

}
